Functional Data-Structure

Definition of Functional Data-Structure
Pattern matching

Definition of Functional Data-Structure

오직 순수 함수만으로 조작되는 자료구조. 순수 함수는 자료를 그 자리에서 변경하거나 기타 side effect를 수행하는 일이 없어야 함. 따라서 함수적 자료구조는 정의에 의해 immutable함.



In [1]:

    
/* 
    Data Type(자료형식)을 도입할 때는 trait(특질) 키워드를 사용 
    trait는 일종의 추상 인터페이스, 필요하면 메서드도 구현할 수 있음.
    sealed 키워드는 이 trait의 모든 구현이 반드시 이 파일 안에 정의되어 있어야함을 뜻함.
*/

// Singly linked list
sealed trait List[+A]  // 형식 A에 대해 매개변수화된 List자료 형식, 
                       // A앞에 있는 '+'는 가변 지정자(variance annotaion). '+'가 붙으면 공변(covariant)
                       // '+'가 붙어 있지 않으면 불변(invariant)
case object Nil extends List[Nothing]  // 빈 리스트를 나타내는 List 자료 생성자
case class Cons[+A](head: A, tail: List[A]) extends List[A] // 비지 않은 리스트를 나타내는 List 자료 생성자. tail은 또 다른 Cons or Nil

// List의 Companion object (trait와 이름이 같은 객체)
// List의 생성과 조작을 위한 함수들을 담는다.
object List {
    def sum(ints: List[Int]): Int = ints match {  // 패턴 매치를 이용해서 정수 List의 합을 구하는 함수
        case Nil => 0  // 빈 리스트 Nil의 경우 0을 리턴
        case Cons(x, xs) => x + sum(xs)  // head가 x인 리스트는 x 더하기 tail의 합
    }
    
    def product(ds: List[Double]): Double = ds match {
        case Nil => 1.0
        case Cons(0.0, _) => 0.0
        case Cons(x, xs) => x * product(xs)
    }
    
    def apply[A](as: A*): List[A] =   // A* 는 가변 인수를 나타냄 타입이 A인 인수를 여러개 받음 ','로 구분
        if(as.isEmpty) Nil
        else Cons(as.head, apply(as.tail: _*))
}









    Out[1]:





defined trait List
defined object Nil
defined class Cons
defined object List



In [2]:

    
List(1,2,3,4,5)









    Out[2]:





res1: List[Int] = Cons(1,Cons(2,Cons(3,Cons(4,Cons(5,Nil)))))



In [3]:

    
List.sum(res1)









    Out[3]:





res2: Int = 15



In [4]:

    
val ex1: List[Double] = Nil
val ex2: List[Int] = Cons(1, Nil)
val ex3: List[String] = Cons("a", Cons("b", Nil))









    Out[4]:





ex1: List[Double] = Nil
ex2: List[Int] = Cons(1,Nil)
ex3: List[String] = Cons(a,Cons(b,Nil))

Pattern Matching

target과 일치하는 패턴에 해당하는 결과를 리턴하는 구문. 위에 있는 패턴부터 검증, 여러 패턴과 일치하는 경우 위에서 부터 검증하기 때문에 최상위에 있는 패턴의 결과를 리턴함.

target match {
    case pattern1 => result
    case pattern2 => result
    ...
}

패턴은 3이나 "hi" 같은 리터럴과 x나 xs같이 소문자나 밑줄로 시작하는 식별자로 된 변수, 그리고 Cons(x, xs)나 Nil같은 자료 생성자로 구성됨. 변수는 모든 것에 부합하는 반면 자료 생성자는 해당 형태의 값에만 부합.



In [5]:

    
// Pattern Matching Example
List(1,2,3) match { case _ => 42 }
List(1,2,3) match { case Cons(h, _) => h }
List(1,2,3) match { case Cons(_, t) => t }
// List(1,2,3) match { case Nil => 42}









    Out[5]:





res4_0: Int = 42
res4_1: Int = 1
res4_2: List[Int] = Cons(2,Cons(3,Nil))

연습문제 3.1

다음 패턴 부합 표현식의 결과는 무엇인가?

val x = List(1,2,3,4,5) match {
  case Cons(x, Cons(2, Cons(4, _))) => x
  case Nil => 42
  case Cons(x, Cons(y, Cons(3, Cons(4, _)))) => x + y
  case Cons(h,t) => h + sum(t)
  case _ => 101
}

연습문제 3.2

List의 첫 요소를 제거하는 함수 tail을 구현하라. 이 함수가 상수 시간으로 실행됨을 주의할 것. Nil인 List도 지원하도록 독자의 구현을 수정하는 여러 가지 방법들도 고려해 보라. 이에 대해서는 다음 장에서 좀 더 살펴볼 것이다.



In [6]:

    
def tail[A](as: List[A]): List[A] = as match {
    case Nil => throw new UnsupportedOperationException
    case Cons(_, t) => t
}









    Out[6]:





defined function tail



In [7]:

    
tail(List(1,2,3,4))









    Out[7]:





res6: List[Int] = Cons(2,Cons(3,Cons(4,Nil)))

연습문제 3.3

같은 맥락에서, List의 첫 요소를 다른 값으로 대체하는 함수 setHead를 구현하라.



In [8]:

    
def setHead[A](l: List[A], x: A): List[A] = l match {
  case Nil => throw new UnsupportedOperationException
  case Cons(h, t) => Cons(x, t)
}









    Out[8]:





defined function setHead



In [9]:

    
setHead(List(1,2,3), 8)









    Out[9]:





res8: List[Int] = Cons(8,Cons(2,Cons(3,Nil)))

연습문제 3.4

tail을 일반화해서, 목록에서 처음 n개의 요소를 제거하는 함수 drop을 구현하라. 이 함수의 실행 시간은 제거되는 원소의 개수에만 비례함을 주의할 것. List 전체의 복사본을 만들 필요는 없다.

def drop[A](l: List[A], n: Int): List[A]



In [10]:

    
def drop[A](l: List[A], n: Int): List[A] = {
  def loop[A](as: List[A], n: Int): List[A] = 
    if(n>0) loop(tail(as), n-1)
    else as
  loop(l, n)
}









    Out[10]:





defined function drop



In [11]:

    
drop(List(1,2,3,4,5), 2)









    Out[11]:





res10: List[Int] = Cons(3,Cons(4,Cons(5,Nil)))

연습문제 3.5

주어진 조건과 부합하는 List의 앞 요소들(prefix)을 제거하는 함수 dropWhile을 구현하라.

def dropWhile[A](l: List[A], f: A => Boolean): List[A]



In [12]:

    
def dropWhile[A](l: List[A], f: A => Boolean): List[A] = l match {
  case Nil => Nil
  case Cons(h, t) if(f(h)) => dropWhile(t, f)
  case _ => l
}









    Out[12]:





defined function dropWhile



In [13]:

    
dropWhile(List(1,2,3,4,5), ((x: Int) => x % 2 == 0))









    Out[13]:





res12: List[Int] = Cons(1,Cons(2,Cons(3,Cons(4,Cons(5,Nil)))))

연습문제 3.6

한 List의 마지막 요소를 제외한 모든 요소로 이루어진 List를 돌려주는 함수 init을 구현하라. 예를 들어 List(1,2,3,4)에 대해 init은 List(1,2,3)을 돌려주어야 한다. 이 함수를 tail처럼 상수 시간으로 구현할 수 없는 이유는 무엇일까?

def init[A](l: List[A]): List[A]



In [14]:

    
def init[A](l: List[A]): List[A] = l match {
  case Cons(_, Nil) => Nil
  case Cons(h, t) => Cons(h, init(t))
}

// 리스트의 첫 원소인 head는 바로 접근이 가능하지만
// tail은 앞에서 부터 차례대로 접근해야하기 때문에 리스트의 길이만큼의 시간이 걸림









    Out[14]:





defined function init



In [15]:

    
init(List(1,2,3,4))









    Out[15]:





res14: List[Int] = Cons(1,Cons(2,Cons(3,Nil)))

2017-09-15 [29th]

고차 함수로의 일반화

def sum(ints: List[Int]): Int = ints match {  
    case Nil => 0  // 빈 리스트 Nil의 경우 0을 리턴
    case Cons(x, xs) => x + sum(xs)  // head가 x인 리스트는 x 더하기 tail의 합
}

def product(ds: List[Double]): Double = ds match {
    case Nil => 1.0 // 빈 리스트 Nil의 경우 1.0을 리턴
    case Cons(x, xs) => x * product(xs) // head가 x인 리스트는 x 곱하기 tail의 곱
}

위와 같이 리스트를 다루는 함수는 비슷한 형태를 취하고 있음 이를 기반으로 함수를 일반화함



In [16]:

    
// 재귀 호출 형태의 함수들을 일반화한 foldRight 함수
def foldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B = as match {
    case Nil => z
    case Cons(x, xs) => f(x, foldRight(xs, z)(f))
}

// foldRight를 활용해서 재구현한 sum 함수와 product 함수
def sum2(ns: List[Int]): Int =
    foldRight(ns, 0)((x, y) => x + y)

def product2(ns: List[Double]): Double =
    foldRight(ns, 1.0)(_ * _)









    Out[16]:





defined function foldRight
defined function sum2
defined function product2



In [17]:

    
val intList = List(1,2,3)
sum2(intList)









    Out[17]:





intList: List[Int] = Cons(1,Cons(2,Cons(3,Nil)))
res16_1: Int = 6

위 sum2의 호출 구조를 트레이스 해보면 다음과 같음

foldRight(Cons(1, Cons(2, Cons(3, Nil))), 0)((x,y) => x + y)
1 + foldRight(Cons(2, Cons(3, Nil)), 0)((x,y) => x + y)
1 + (2 + foldRight(Cons(3, Nil), 0)((x,y) => x + y))
1 + (2 + (3 + (foldRight(Nil, 0)((x,y) => x + y))))
1 + (2 + (3 + (0)))
6

연습문제 3.7

foldRight로 구현된 product2가 0.0을 만났을 때 즉시 재귀를 멈추고 0.0을 돌려줄까? 왜 그럴까? 아니라면 왜 아닐까? foldRight를 긴 목록으로 호출했을 때 어떤 평가 단축이 어떤 식으로 일어나는지 고찰하라. 이는 다른 연습문제들보다 심오한 문제이며, 제5장에서 다시 살펴볼 것이다.

연습문제 3.8

foldRight(List(1,2,3), Nil: List[Int])(Cons(_,_))처럼 Nil과 Cons 자체를 foldRight에 전달하면 어떤 일이 발생할까? 이로부터, foldRight와 List의 자료 생성자들 사이의 관계에 관해 어떤 점을 알 수 있는가?

연습문제 3.9

foldRight를 이용해서 목록의 길이를 계산하라.

def length[A](as: List[A]): Int



In [18]:

    
def length[A](as: List[A]): Int = 
    foldRight(as, 0)((_, x) => x + 1)









    Out[18]:





defined function length



In [19]:

    
length(List(1,2,3,4,5))









    Out[19]:





res18: Int = 5

2017-09-24 [30th]

연습문제 3.10

이번 절의 foldRight 구현은 꼬리 재귀가 아니므로 긴 목록에 대해서는 StackOverflowError 오류가 발생한다(이를 "스택에 안전[stack-safe]하지 않다"라고 말한다). 실제로 그런지 실험해 보고, 꼬리 재귀적인 또 다른 일반적 목록 재귀 함수 foldLeft를 이전 장에서 논의한 기법들을 이용해서 작성하라. 서명은 다음과 같다.

def foldLeft[A,B](as: List[A], z: B)(f: (B, A) => B): B



In [20]:

    
def foldLeft[A,B](as: List[A], z: B)(f: (B, A) => B): B = as match {
    case Nil => z
    case Cons(x, xs) => foldLeft(xs, f(z, x))(f)
}









    Out[20]:





defined function foldLeft

연습문제 3.11

sum, product와 목록의 길이를 계산하는 함수를 foldLeft를 이용해서 작성하라.



In [21]:

    
def sumViaFL(as: List[Int]): Int = 
    foldLeft(as, 0)((x, a) => x + a)

def prodViaFL(as: List[Double]): Double =
    foldLeft(as, 1.0)((x, a) => x * a)

def lengthViaFL[A](as: List[A]): Int =
    foldLeft(as, 0)((x, _) => x + 1)









    Out[21]:





defined function sumViaFL
defined function prodViaFL
defined function lengthViaFL

연습문제 3.12

목록의 역을 돌려주는(이를테면 List(1,2,3)에 대해 List(3,2,1)을 돌려주는) 함수를 작성하라. 접기(fold) 함수를 이용해서 작성할 수 있는지 시도해 볼 것.



In [22]:

    
def reverse[A](as: List[A]): List[A] =
    foldLeft(as, Nil: List[A])((z, x) => Cons(x, z))









    Out[22]:





defined function reverse

연습문제 3.13 (Hard)

foldLeft를 foldRight를 이용해서 구현할 수 있을까? 그 반대 방향은 어떨까? foldLeft를 이용하면 foldRight를 꼬리 재귀적으로 구현할 수 있으므로 긴 목록에 대해서도 스택이 넘치지 않는다는 장점이 생긴다.



In [23]:

    
def foldLeft2[A,B](as: List[A], z: B)(f: (B, A) => B): B =
  foldRight(as, (b:B) => b)((a, g) => b => g(f(b,a)))(z)

def foldRight2[A,B](as: List[A], z:B)(f: (A, B) => B): B =
  foldLeft(as, (b:B) => b)((g, a) => b => g(f(a,b)))(z)









    Out[23]:





defined function foldLeft2
defined function foldRight2

연습문제 3.14

append(한 List 뒤에 다른 List를 붙이는 것)를 foldLeft나 foldRight를 이용해서 구현하라.



In [24]:

    
def append[A](a1: List[A], a2: List[A]): List[A] =
    foldRight(a1, a2)(Cons(_, _))









    Out[24]:





defined function append

연습문제 3.15 (Hard)

목록들의 목록을 하나의 목록으로 연결하는 함수를 작성하라. 실행 시간은 반드시 모든 목록의 전체 길이에 선형으로 비례해야한다. 이미 정의한 함수들을 활용하도록 노력할 것.

def concat[A](aa: List[List[A]]): List[A]



In [25]:

    
def concat[A](aa: List[List[A]]): List[A] = 
    foldRight(aa, Nil: List[A])(append(_, _))









    Out[25]:





defined function concat



In [25]:

    
foldRight(aa, Nil: List[A])(List(1,2,3,4)))









    



SyntaxError: found ")", expected Semis | End | BacktickId | PlainId | WL ~ "." ~/ Id | WL ~ TypeArgs | NotNewline ~ ArgList at index 42
t[A])(List(1,2,3,4)))
                    ^

연습문제 3.16

정수 목록의 각 요소에 1을 더해서 목록을 변환하는 함수를 작성하라. (주의 새 List를 돌려주는 순수 함수이어야 한다.)

def inc(ai: List[Int]): List[Int]



In [26]:

    
def inc(ai: List[Int]): List[Int] =
    foldRight(ai, Nil: List[Int])((x, z) => Cons(x + 1 , z))









    Out[26]:





defined function inc



In [27]:

    
inc(List(1,2,3))









    Out[27]:





res26: List[Int] = Cons(2,Cons(3,Cons(4,Nil)))

2017-09-30 [31th]

연습문제 3.16 +

정수 목록의 각 요소에 정수 n을 더해서 목록을 변환하는 함수를 작성하라. (주의 새 List를 돌려주는 순수 함수이어야 한다.)



In [28]:

    
def incN(ai: List[Int], n: Int): List[Int] =
    foldRight(ai, Nil: List[Int])((x, z) => Cons(x + n , z))









    Out[28]:





defined function incN



In [29]:

    
incN(List(1,2,3), 3)









    Out[29]:





res28: List[Int] = Cons(4,Cons(5,Cons(6,Nil)))

연습문제 3.17

List[Double]의 각 값을 String으로 변환하는 함수를 작성하라. d: Double을 String으로 변환할 때에는 d.toString이라는 표현식을 사용하면 된다.

def doubleToString(ds: List[Double]): List[String]



In [30]:

    
def doubleToString(ds: List[Double]): List[String] =
    foldRight(ds, Nil: List[String])((h, t) => Cons(h.toString, t))









    Out[30]:





defined function doubleToString



In [31]:

    
doubleToString(List(1.2, 3.4))









    Out[31]:





res30: List[String] = Cons(1.2,Cons(3.4,Nil))

연습문제 3.18

List의 구조를 유지하면서 List의 각 요소를 수정하는 작업을 일반화한 함수 map을 작성하라. 서명은 다음과 같다.

def map[A,B](as: List[A])(f: A => B): List[B]



In [32]:

    
// def foldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B
// def inc(as: List[Int]): List[Int] =
//     foldRight(as, Nil: List[Int])((h, t) => Cons(h + 1 , t))

// def doubleToString(as: List[Double]): List[String] =
//     foldRight(as, Nil: List[String])((h, t) => Cons(h.toString, t))

def map[A,B](as: List[A])(f: A => B): List[B] =
    foldRight(as, Nil: List[B])((h, t) => Cons(f(h), t))









    Out[32]:





defined function map

연습문제 3.19

List에서 주어진 술어를 만족하지 않는 요소들을 제거하는 함수 filter를 작성하라. 그리고 그 함수를 이용해서 List[Int]에서 모든 홀수를 제거하라.

def filter[A](as: List[A])(f: A => Boolean): List[A]



In [33]:

    
def filter[A](as: List[A])(f: A => Boolean): List[A] =
    foldRight(as, Nil: List[A])((h, t) => if(f(h)) Cons(h, t) else t)









    Out[33]:





defined function filter



In [34]:

    
filter(List(1,2,3,4))(x => x % 2 == 0)









    Out[34]:





res33: List[Int] = Cons(2,Cons(4,Nil))

연습문제 3.20

map과 비슷하되 하나의 요소가 아니라 List를 최종 결과 List에 삽입하는 함수 flatMap을 작성하라. 서명은 다음과 같다.

def flatMap[A,B](as: List[A])(f: A => List[B]): List[B]

예를 들어 flatMap(List(1,2,3))(i => List(i,i))는 List(1,1,2,2,3,3)이 되어야 한다.



In [35]:

    
def flatMap[A,B](as: List[A])(f: A => List[B]): List[B] =
    foldRight(as, Nil: List[B])((h, t) => append(f(h), t))

def flatMap_[A,B](as: List[A])(f: A => List[B]): List[B] =
    concat(map(as)(f))









    Out[35]:





defined function flatMap
defined function flatMap_



In [36]:

    
map(List(1,2,3))(i => List(i,i))









    Out[36]:





res35: List[List[Int]] = Cons(Cons(1,Cons(1,Nil)),Cons(Cons(2,Cons(2,Nil)),Cons(Cons(3,Cons(3,Nil)),Nil)))

연습문제 3.21

flatMap을 이용해서 filter를 구현하라.



In [37]:

    
def filter[A](as: List[A])(f: A => Boolean): List[A] =
    flatMap(as)(a => if(f(a)) Cons(a, Nil) else Nil)









    Out[37]:





defined function filter



In [38]:

    
filter(List(1,2,3,4))(x => x % 2 == 0)









    Out[38]:





res37: List[Int] = Cons(2,Cons(4,Nil))



In [ ]: